package leetcode_core.leetcode_7;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月24日 19:50
 */
public class CanFinish {
    private boolean[] visited;
    private boolean[] onPath;
    private boolean hadCycle;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        //1. 建图
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //2. 对图进行搜素,看是否有环
        for(int i = 0;i<numCourses;i++){
            traverse(graph,i);
        }
        //3. 返回结果
        return hadCycle;
    }


    private void traverse(List<Integer>[] graph,int s){
        if(onPath[s]){
            hadCycle = true;
            return;
        }
        if(hadCycle || visited[s]){
            return;
        }
        //标记当前节点已经被访问过
        visited[s] = true;
        //将当前节点加入到当前访问路径中
        onPath[s] = true;
        //继续遍历
        for (Integer node : graph[s]) {
            traverse(graph,node);
        }
        onPath[s] = false;
    }

    /**
     * 这里建立的是一个被依赖的关系,也就是说,通过map[i]->target
     * 它的含义是说:只有先完成i才能完成target
     * @param prerequisites:它的含义是说,你只有完成了[1],才能完成[0]
     * @return
     */
    private List<Integer>[] buildGraph(int numCourses,int[][] prerequisites){
        //1. 建立图的负载
        List<Integer>[] graph = new ArrayList[numCourses];
        //2. 初始化图
        for(int i = 0;i<numCourses;i++){
            graph[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            //from边
            int from = prerequisite[1];
            //to边
            int to = prerequisite[0];
            //添加一条从from指向to的有向边
            graph[from].add(to);
        }
        return graph;
    }
}
